Міністерство освіти і науки України
Національний університет „Львівська політехніка”
Кафедра ЕОМ
Звіт
до курсової роботи (Частина 2)
з дисципліни: “ Програмування. Частина III. Структури даних та алгоритми ”
Процес знаходження номеру варіанта індивідуального завдання
Вибір АТД:
№ = [(день народження) + (місяць народження) + (ASCII–код першої літери прізвища – велика латинська літера) ] % 3 + 1 = [(26) + (11) + (75) ] % 3 + 1 = 2
Примітка: 1 – стек, 2 – черга, 3- список.
Вибір номера завдання:
№ = [(день народження) + (ASCII–код першої літери прізвища – велика латинська літера) ] % 10 + 1 =
= [(26) + (75) ] % 10 + 1 =2
Зміст
1. Теоретична частина 3
2. Частина 1. Побудова АТД 5
2. 1. Постановка задачі 5
2. 2. Динаміка вмісту 5
2. 3. Результати виконання програми 6
3. Частина 2. Застосування АТД 7
3.1. Постановка задачі 7
3.2. Алгоритм розв’язання задачі 7
3.3. Результати виконання програми 8
Висновки 9
Список літератури 10
Додатки 11
1.Теоретична частина
СТЕК
Стек - динамічна структура даних, що представляє собою впорядкований набір елементів, у якій додавання нових елементів і видалення існуючих відбувається з одного кінця, який називається вершиною стека. Згідно визначення, елементи вилучаються зі стека в порядку, зворотному їхньому додаванню в цю структуру, тобто діє принцип LIFO (Last In, Fist Out – останнім прийшов, першим вийшов).
Найбільш наочним прикладом організації стека служить дитяча пірамідка, в якій додавання й зняття кілець здійснюється саме відповідно до визначення стека. Можна уявити також стопку тарілок. Нижня тарілка із цієї стопки буде використана останньою, а верхня тарілка, яка була покладена в стопку останньою, буде використана першою. Подібне відбувається й в стеку.
Стеки широко використовуються як для розв’язання прикладних задач, так і в системному програмному забезпеченні, включаючи компілятори і інтерпретатори.
Історично склалося так, що дві основні операції для стека - помістити в стек і вилучити зі стека - одержали назву відповідно "заштовхнути" і "виштовхнути". Тому для реалізації стека необхідно створити дві функції: "push" (заштовхнути), що поміщає елемент у вершину стека, і "pop" (виштовхнути), що вилучає з вершини стека один елемент. Необхідно також передбачити певну область у пам'яті, де фактично буде зберігатися стек. Для цього можна використати масив або можна виділити область пам'яті, використовуючи засоби динамічного розподілу пам'яті.
ЧЕРГА
Чергою FІFO (Fіrst - Іn - Fіrst- Out - "першим прийшов - першим вийшов") називається така послідовність зі змінною довжиною, у якій додавання елементів виконується тільки з однієї сторони (цю сторону часто називають кінцем або хвостом черги), а вилучення - з іншої сторони (називають початком або головою черги). Ті самі черги до прилавків і до кас, які ми так не любимо, є типовим побутовим прикладом черги FІFO.
Основні операції над чергою - ті ж, що й над стеком - додавання, вилучення, визначення розміру, читання, що не руйнує чергу.
Дек - особливий вид черги. Дек (від англ. deq - double ended queue, тобто черга із двома кінцями) - це така послідовність, у якій як додавання, так і вилучення елементів може здійснюватися з кожного із двох кінців. Окремі випадки дека - дек з обмеженим входом і дек з обмеженим виходом. Логічна й фізична структури дека аналогічні логічній і фізичній структурі кільцевої FіFO-черги. Однак, стосовно до дека доцільно говорити не про початок і кінець, а про лівий і правий кінці. Динамічна реалізація дека є об'єднанням стека і черги.
Основні операції над деком:
додавання элемента справа;
додавання элемента слева;
вилучення элемента справа;
вилучення элемента слева;
Задачі, що вимагають використання структури дека, зустрічаються в обчислювальній техніці...
